Spectral graph sparsification is a classical tool for reducing graph complexity while preserving Laplacian quadratic forms. In graph neural networks (GNNs), sparsification is often used to accelerate computation while maintaining predictive performance. In this work, we study a complementary representation-level question: does sparsification preserve the geometry of learned embeddings? For polynomial-filter GNNs, we prove that any $ε$-spectral sparsifier induces $O(ε)$ perturbations in polynomial graph filters, multilayer hidden representations, and their Gram matrices. These guarantees imply stability of squared pairwise distances, class means, and covariance structure in embedding space. We further establish finite-time training stability: under smoothness and boundedness assumptions, gradient descent on dense and sparsified graphs produces weight trajectories whose separation grows at most proportionally to the sparsification distortion. Empirically, effective-resistance sparsification validates the predicted perturbation chain on synthetic graphs and preserves hidden representation geometry on real datasets. In our experiments, the gram matrix and training dynamics show low divergence even under substantial sparsification, consistent with the predicted stability under spectral sparsification. Hidden Gram preservation strongly predicts neighborhood preservation and class-centroid stability across FashionMNIST, Cora, and Paul15. Together, these results show that spectral sparsification preserves not only graph operators, but also the representation geometry that supports downstream use of GNN embeddings for interpretability.

The appendix includes the missing proofs, detailed discussions of some argument in the main body483 and more numerical experiments. We organize the appendix as follows:484 The proof of infeasibility condition (Theorem 3.2) is provided in Section B.485 Explanations on conditions derived in Theorem 3.2 are included in Section C.486 The proof of properties of the proposed model (r)LogSpecT (Proposition 3.4 & 3.6) is given487 in Section D and some additional properties are discussed.488 The truncated Hausdorff distance based proof details of Theorem 4.1 and Corollary 4.4 are489 given in Section E.490 Details of L-ADMM and its convergence analysis are in Section F.491 Additional experiments and discussions on synthetic data are included in Section G.492 Since the linear system (4) has no solution, we know from Farkas' lemma that the following system494 Hence, S is also a solution to (13). However, (13) does not have a solution. We can conclude that504 rSpecT is infeasible in this case.505

A.1 Proof of Theorem 1 Before proofing Theorem 1, We first demonstrate the superiority of even-hop neighbors over odd-hop neighbors from the perspective of random walks. In a binary node classification task, denote the probability of a random walk of length k that starts and ends with nodes of the same label as pk,k > 0. Suppose the edge homophily level his a random variable that belongs to a uniform distribution in [0,1] and p1 = h, then: Lemma 1. If k is odd, Eh[pk] = 12. If k is even, Eh[pk] 12. Proof. We now provide a brief discussion of the superiority of even-hop neighbors in multi-class node classification tasks following [14].

Graph Neural Networks (GNNs) have received extensive research attention for their promising performance in graph machine learning. Despite their extraordinary predictive accuracy, existing approaches, such as GCN and GPRGNN, are not robust in the face of homophily changes on test graphs, rendering these models vulnerable to graph structural attacks and with limited capacity in generalizing to graphs of varied homophily levels. Although many methods have been proposed to improve the robustness of GNN models, the majority of these techniques are restricted to the spatial domain and employ complicated defense mechanisms, such as learning new graph structures or calculating edge attention. In this paper, we study the problem of designing simple and robust GNN models in the spectral domain. We propose EvenNet, a spectral GNN corresponding to an even-polynomial graph filter. Based on our theoretical analysis in both spatial and spectral domains, we demonstrate that EvenNet outperforms full-order models in generalizing across homophilic and heterophilic graphs, implying that ignoring odd-hop neighbors improves the robustness of GNNs. We conduct experiments on both synthetic and real-world datasets to demonstrate the effectiveness of EvenNet. Notably, EvenNet outperforms existing defense models against structural attacks without introducing additional computational costs and maintains competitiveness in traditional node classification tasks on homophilic and heterophilic graphs.

The proof of infeasibility condition (Theorem 3.2) is provided in Section B. Explanations on conditions derived in Theorem 3.2 are included in Section C. The proof of properties of the proposed model (r)LogSpecT (Proposition 3.4 The truncated Hausdorff distance based proof details of Theorem 4.1 and Corollary 4.4 are Details of L-ADMM and its convergence analysis are in Section F. Additional experiments and discussions on synthetic data are included in Section G. ( m 1) Again, from Farkas' lemma, this implies that the following linear system does not have a solution: Example 3.1 we know δ = 2|h Since the constraint set S is a cone, it follows that for all γ > 0, γ S = S . Opt(C, α) = α Opt(C, 1), which completes the proof. The proof will be conducted by constructing a feasible solution for rLogSpecT. Since the LogSpecT is a convex problem and Slater's condition holds, the KKT conditions We show that it is feasible for rLogSpecT. R, its epigraph is defined as epi f: = {( x, y) | y f ( x) }. Before presenting the proof, we first introduce the following lemma.

Neural Information Processing Systems http://nips.cc/